/*
 * graphe.h
 *
 *  Created on: 3 juin 2009
 *      Author: hissel
 */

#ifndef GRAPHE_H_
#define GRAPHE_H_

#include	<iostream>
#include	<string>
#include	<vector>
#include	<list>
#include	<functional>
#include	<exception>
#include	"heap.h"

using namespace std;

class Arc;

struct Comparateur;

/**
 * \class GrapheException
 * \brief Exception soulevée lorsqu'une erreur survient pendant une opération sur les graphes
 *
 * La classe permet de gérer les erreurs d'utilisation des opérations sur les graphes.
 */
class GrapheException:public exception {
	public:
		/**
		 * \brief Ensemble des codes d'erreur possibles
		 *
		 * L'énumération rassemble les codes d'erreur qui peuvent être retournés lorsqu'une opération sur les graphes a généré une erreur.
		 */
		enum Code {
			NO_VERTEX,	//!< Sommet introuvable
			NO_EDGE	//!< Arête introuvable
			} code;	//!< Code de l'erreur
		string message;	//!< Message décrivant l'erreur
		GrapheException(Code pcode):code(pcode) {}	//!< Constructeur d'exception sans message de sortie
		GrapheException(Code pcode,string pmessage):code(pcode),message(pmessage) {}	//!< Constructeur d'exception avec message de sortie
		~GrapheException() throw() {}	//!< Destructeur standard
		const char* what() const throw();	//!< Retourne un message descriptif de l'exception
};

/**
 * \class Sommet
 * \brief Sommet d'un graphe orienté
 *
 * Le sommet est l'entité de base des graphes orientés. Il est relié à des arcs.
 */
class Sommet {
	public:
		friend class Graphe;
		int id;	//!< Identifiant du sommet
		string nom;	//!< Nom du sommet
		double dist;	//!< Distance au sommet de départ, utilisée dans l'algorithme de Dijkstra. dist représente également la distance minimale du sommet à l'une des origines dans la procédure Graphe::dijkstra_graphe.
		double fdist;	//!< Distance estimée entre le départ et l'arrivée, par le chemin courant. fdist est utilisée par l'algorithme A* pour s'orienter a priori vers la bonne direction en s'appuyant sur une estimation de la distance à l'arrivée donnée par la fonction estimate_distance.
		list<Arc*> arcs;	//!< Liste des arcs qui ont pour origine le sommet

		/**
		 * \brief Statut du sommet
		 *
		 * La variable statut est utilisée par certains algorithmes relatifs au traitement des graphes, notamment l'algorithme de Dijkstra et son pendant A*, et par l'algorithme d'optimisation de tournée.
		 * Dans l'algorithme de Dijkstra,
		 * 	- statut = 0 si le sommet n'a pas encore été parcouru par l'algorithme
		 * 	- statut = 1 s'il a été parcouru (et dist vaut alors exactement la distance minimale)
		 * 	- statut = 2 s'il est en cours de parcours
		 * 	- statut = 3 si le sommet n'a pas été parcouru mais la distance à ses voisins a déjà été évaluée.
		 *
		 * Dans l'algorithme d'optimisation de tournée,
		 * 	- statut = 0 si le sommet n'a pas encore été visité pendant le parcours du graphe
		 * 	- statut = 1 si le sommet a déjà été visité
		 */
		int statut;

		Sommet(int pid,const string pnom):id(pid),nom(pnom),statut(0) {}	//!< Constructeur standard
		Sommet(const Sommet &s):id(s.id),nom(s.nom),dist(s.dist),fdist(s.fdist),statut(0) {}	//!< Constructeur de copie

		/**
		 * \brief Dans le cas des graphes non orientés, renvoie le voisin du sommet par l'arête *a .
		 *
		 * Pour les graphes orientés, cette fonction n'a pas de sens.
		 * \param *a Arc considéré, qui doit avoir pour extrémité le sommet considéré
		 * \return Retourne la seconde extrémité de l'arc *a à l'opposé du sommet considéré.
		 */
		Sommet* voisin(const Arc *a) const;
		static bool compare(const Sommet *s1,const Sommet *s2) {return s1->id<s2->id;}	//!< Fonction de comparaison entre deux sommets utilisée pour l'indexage de la liste et l'accélération de la recherche des sommets.
		virtual void affiche(ostream& out) const;	//!< Affichage sur le flux de sortie out
		virtual ~Sommet() {}	//!< Destructeur standard

		/**
		 * \brief Après un calcul de desserte, retourne la source correspondante au sommet courant
		 *
		 * La fonction ne doit être utilisée qu'après un calcul de desserte par l'algorithme Graphe::desserte. Elle retourne alors la source correspondante au sommet courant.
		 * \return Pointeur vers la source desservant au mieux le sommet courant
		 */
		Sommet* source() const {return (Sommet*)(prec);}
	protected:
		void *prec;	//!< Lors d'un calcul d'itinéraire, prec représente l'arc qui doit mener au sommet dans l'itinéraire optimal. Cette variable est utilisée dans l'algorithme de Dijsktra, afin de reconstituer l'itinéraire global à partir de la destination. Lors d'un calcul de desserte, prec représente la source desservant le sommet courant dans l'algorithme Graphe::desserte
};

/**
 * \brief Retourne 0
 *
 * La fonction retourne toujours 0. Elle est utilisée pour définir une heuristique par défaut dans les procédures de calcul d'itinéraire.
 * \param a Paramètre inusité
 * \param b Paramètre inusité
 * \return Toujours zéro
 */
inline double zero(const Sommet *a,const Sommet *b) {return 0;}

/**
 * \struct Comparateur
 * \brief Structure encapsulant un opérateur de comparaison sur les pointeurs de sommets
 *
 * La structure encapsule un opérateur de comparaison sur les sommets, et définit ainsi une relation d'ordre totale sur l'ensemble des sommets, où un sommet est strictement inférieur à un autre si et seulement si sa distance dist est strictement inférieure.
 * Cette structure est utilisée dans l'algorithme A*, pour la constitution d'un arbre de recherche AVL équilibré.
 */
struct Comparateur:public binary_function<Sommet*,Sommet*,bool> {
	/**
	 * \brief Opérateur de comparaison entre deux sommets
	 */
	bool operator()(const Sommet *a,const Sommet *b) const {
		return a->fdist<b->fdist;
	}
};

/**
 * \class Arc
 * \brief Arc d'un graphe orienté
 *
 * L'arc est caractérisé par sa position, et son poids. Il relie deux sommets.
 */
class Arc {
	public:
		int id;	//!< Identifiant de l'arc
		Sommet *orig;	//!< Sommet à l'origine de l'arc
		Sommet *dest;	//!< Sommet à l'extrémité de l'arc
		double poids;	//!< Poids de l'arc
		bool coupe;	//!< Indique si l'arc est coupé
		string nom;	//!< Nom de l'arc

		/**
		 * \brief Constructeur standard
		 *
		 * Construit un arc sans initialiser ses caractéristiques.
		 */
		Arc():coupe(false) {}

		/**
		 * \fn Arc(int pid,Sommet *ps1,Sommet *ps2,double ppoids,string pnom)
		 * \brief Constructeur standard
		 *
		 * Construit un arc à partir de la donnée de son identifiant pid, de ses extrémités *ps1 et *ps2, de son poids ppoids et de son nom pnom.
		 * \param pid Identifiant
		 * \param *ps1 Sommet d'origine de l'arc
		 * \param *ps2 Sommet extrémité de l'arc
		 * \param ppoids Poids 
		 * \param pnom Nom
		 */
		Arc(int pid,Sommet *ps1,Sommet *ps2,double ppoids,const string pnom):id(pid),orig(ps1),dest(ps2),poids(ppoids),coupe(false),nom(pnom) {}

		Arc(const Arc &a):id(a.id),orig(a.orig),dest(a.dest),poids(a.poids),coupe(a.coupe),nom(a.nom) {}	//!< Constructeur de copie

		virtual ~Arc() {}	//!< Destructeur standard
		static bool compare(const Arc *a1,const Arc *a2) {return a1->id<a2->id;}	//!< Fonction de comparaison entre deux arcs utilisée pour l'indexage de la liste et l'accélération de la recherche des arcs
		virtual void affiche(ostream &out) const;	//!< Affichage sur le flux de sortie out
};

/**
 * \class Graphe
 * \brief Graphe orienté
 *
 * Un graphe orienté est composé de sommets et d'arcs qui joignent deux sommets. Voir aussi les classes Arc et Sommet pour plus d'informations. Cette classe est la structure de base pour les analyses abstraites de réseaux, elle ne comporte pas de composante cartographique et peut être utilisée pour tout type de réseau.
 * Les algorithmes sous-jacents de calcul d'itinéraires, de calcul de desserte, ou d'optimisation de tournée supposent tous que les poids des arcs sont positifs ou nuls.
 */
class Graphe {
	public:
		vector<Sommet*> sommets;	//!< Liste des sommets du graphe
		vector<Arc*> arcs;	//!< Liste des arcs du graphe

		/**
		 * \fn ~Graphe()
		 * Destructeur standard
		 *
		 * Le destructeur appelle la fonction vide() qui libère les ressources contenues dans le graphe. Toutes les structures de données incluses sont libérées et ne doivent plus être passées à \e delete.
		 */
		virtual ~Graphe();

		/**
		 * \fn void vide()
		 * \brief Vide le graphe et libère la mémoire occupée par les sommets et les arcs
		 *
		 * La fonction se charge de libérer toute la mémoire allouée par le graphe. Les structures de données contenues dans le graphe ne doivent pas être libérées par des appels à \e delete ultérieurs.
		*/
		void vide();

		/**
		 * \brief Lit un graphe à partir d'un fichier
		 *
		 * Une structure de graphe est créée à partir d'un fichier texte donné en paramètre. La structure du fichier est la suivante :<br>
		 * \e num_sommet \e nom<br>
		 * \e num_sommet \e nom<br>
		 * ...<br>
		 * ***********<br>
		 * \e num_arc \e num_sommet1 \e num_sommet2 \e poids \e nom<br>
		 * \e num_arc \e num_sommet1 \e num_sommet2 \e poids \e nom<br>
		 * ...<br>
		 * <br>
		 * \param filename Nom du fichier à ouvrir
		 * \param oriente Si la valeur est vraie (par défaut), le graphe est un graphe orienté. Sinon les arcs peuvent être parcourus indifféremment dans les deux sens.
		 */
		void lecture(char *filename,bool oriente=true);

		/**
		 * \brief Recherche d'un élément par dichotomie dans le tableau
		 *
		 * La fonction suppose que la liste est triée par ordre croissant des identifiants. L'élément d'identifiant pid est recherché par dichotomie dans le tableau, avec une complexité en \f$ O(n\log n)\f$.
		 * \param pid Identifiant de l'élément
		 * \return Sommet pointé par l'élément d'identifiant pid, 0 si le sommet n'est pas trouvé
		 */
		Sommet* cherche(int pid) const;

		/**
		 * \brief Calcul des distances minimales de tous les sommets du réseau à un ensemble de sommets déterminés
		 *
		 * La fonction prend en argument un ensemble de sommets d'origine, qui peuvent correspondre par exemple à des lieux stratégiques pour la gestion de crise (services de secours, hôpitaux, pompes...). Elle calcule la distance minimale de chacun des sommets du graphe à l'un de ces points stratégiques. Les résultats sont stockés dans la variable membre Sommet::dist pour chacun des sommets.
		 * Les distances sont calculées selon l'algorithme de Dijkstra qui a une complexité en O(np), avec n le nombre de sommets du graphe et p le nombre d'arêtes.
		 * \param origines Liste des sommets initiaux à partir desquels les distances doivent être calculées
		 */
		void dijkstra_graphe(list<Sommet*> &origines);

		/**
		 * \brief Recherche du plus court chemin entre *orig et *fin par l'algorithme A*
		 *
		 * La fonction recherche le plus court itinéraire entre *orig et *fin en utilisant l'algorithme A*. Elle retourne la liste des arcs qui composent l'itinéraire.
		 * \param *orig Origine du trajet
		 * \param *fin Destination du trajet
		 * \param heuristique Fonction d'estimation de la distance entre deux sommets, utilisée pour s'orienter intelligemment dans l'ensemble des itinéraires possibles. Pour que l'algorithme renvoie toujours le meilleur itinéraire, cette fonction doit être inférieure à la distance réelle entre les deux sommets.
		 * \return Liste des arcs par où passe l'itinéraire
		 */
		list<Arc*> itineraire(Sommet *orig,Sommet *fin,double (*heuristique)(const Sommet *a,const Sommet *b)=zero);

		/**
		 * \brief Recherche du plus court chemin entre *orig et *fin par l'algorithme A*
		 *
		 * La fonction recherche le plus court itinéraire entre *orig et *fin en utilisant l'algorithme A*. Elle retourne la liste des arcs qui composent l'itinéraire.
		 * \param *orig Index de l'origine du trajet
		 * \param *fin Index de la destination du trajet
		 * \param heuristique Fonction d'estimation de la distance entre deux sommets, utilisée pour s'orienter intelligemment dans l'ensemble des itinéraires possibles. Pour que l'algorithme renvoie toujours le meilleur itinéraire, cette fonction doit être inférieure à la distance réelle entre les deux sommets.
		 * \return Liste des arcs par où passe l'itinéraire
		 */
		list<Arc*> itineraire(int orig,int fin,double (*heuristique)(const Sommet *a,const Sommet *b)=zero) {return itineraire(cherche(orig),cherche(fin),heuristique);}

		/**
		 * \brief Recherche la source desservant chacun des sommets du graphe
		 *
		 * La fonction parcourt le graphe et indique pour chaque sommet dans son membre source la source la plus proche qui le dessert. Cette fonction appelle l'algorithme de Dijkstra pour calculer la distance aux sources de chacun des sommets du graphe, via la fonction dijkstra_graphe().
		 * La complexité de la fonction est O(np) avec n le nombre de sommets et p le nombre d'arêtes du graphe.
		 * \param origines Liste des sources, à savoir les sommets initiaux à partir desquels les distances sont calculées
		 */
		void desserte(list<Sommet*> &origines);

		/**
		 * \brief Recherche le chemin le plus court pour parcourir tous les sommets du graphe à partir du sommet initial spécifié en argument
		 *
		 * La fonction recherche le plus court chemin qui parcourt l'ensemble des sommets du graphe à partir du sommet initial start. Il n'est pas demandé à ce que le chemin constitue un cycle, et l'extrémité finale peut différer de l'extrémité initiale.
		 * L'algorithme utilisé consiste en une recherche systématique de tous les chemins possibles. Sa complexité est donc au pire O(n!) avec n le nombre de sommets du graphe. Le temps de calcul croît très rapidement en fonction du nombre de sommets,
		 * et la fonction ne peut donc raisonnablement être utilisée que pour des graphes dont le nombre de sommets est inférieur à la dizaine. Pour plus de sommets, on préférera les algorithmes utilisant des heuristiques de parcours, tel celui implémenté
		 * par AntGraph::shortest_path.
		 * \param node Sommet initial de la tournée
		 * \return Liste ordonnée des arcs qui composent la tournée optimale
		 */
		list<Arc*> tournee(Sommet *node);
	protected:
		/**
		 * \brief Une itération de l'algorithme A*
		 *
		 * La fonction réalise une itération de l'algorithme A* : elle sélectionne le sommet de poids minimal dans la liste ouverte maintenue passée en argument et le retire de la liste, calcule la distance de ses voisins à l'origine du parcours, et ajoute les voisins à la liste ouverte.
		 * \param fin Destination souhaitée de l'itinéraire
		 * \param visites Liste ouverte des noeuds par lesquels l'algorithme est déjà passé
		 * \param heuristique Fonction d'estimation de la distance entre deux sommets, utilisée pour s'orienter intelligemment dans l'ensemble des itinéraires possibles. Pour que l'algorithme renvoie toujours le meilleur itinéraire, cette fonction doit être inférieure à la distance réelle entre les deux sommets.
		 */
		void sp_iteration(Sommet *fin,Heap<Sommet*,Comparateur> &visites,double (*heuristique)(const Sommet *a,const Sommet *b)=zero);
};

/**
 * Affichage d'un sommet sur un flux de sortie
 */
inline ostream& operator<<(ostream& out,const Sommet &s) {
	s.affiche(out);
	return out;
}

/**
 * Affichage d'un arc sur un flux de sortie
 */
inline ostream& operator<<(ostream& out,const Arc &a) {
	a.affiche(out);
	return out;
}

#endif /* GRAPHE_H_ */
